Due to the nature of the Flash memory of solid state drives (SSD), data cannot be directly overwritten, as is possible in a magnetic hard disk drive. When data is first written to an SSD, all of the cells thereof start in an erased state, enabling data to be written thereto. Data is written in SSDs on a page-basis; typically, 8-16 kilobytes (KB) in size. Conventional SSD controllers, which manage the Flash memory on the SSD and interfaces with the host system, use a Logical-to-Physical (L2P) mapping system known as Logical Block Addressing (LBA) that is part of the Flash Translation Layer (FTL). When new data comes in replacing older data already written, the SSD controller causes the new data to be written in a new location (as the SSD cannot directly overwrite the old data) and updates the logical mapping to point to the new physical location. At this juncture, the old physical location no longer holds valid data. As such, the old physical location will eventually need to be erased before it can be written again.
Conventionally, a dynamic random access memory (DRAM) table is used to store the large L2P map that maps logical entries to physical address locations on the SSD. This large L2P map is usually saved in small sections as writes come in. For example, if random writing occurs, although the system may have to update only one entry, it may nonetheless have to save the entire table or a portion thereof, including entries that have not been updated, which is inherently inefficient.
FIG. 1 shows aspects of a conventional Logical Block Addressing (LBA) scheme for an SSD. As shown therein, a map table 104 contains one entry for every logical block 102 defined for the data storage device's Flash memory 106. For example, a 64 GB SSD that supports 512 byte logical blocks may present itself to the host as having 125,000,000 logical blocks. One entry in the map table 104 contains the current location of each of the 125,000,000 logical blocks in the Flash memory 106. In a conventional SSD, a Flash page holds an integer number of logical blocks (i.e., a logical block does not span across Flash pages). In this conventional example, an 8 KB Flash page would hold 16 logical blocks (of size 512 bytes). Therefore, each entry in the logical-to-physical map table 104 contains a field 108 identifying the flash die on which the logical block is stored, a field 110 identifying the flash block on which the logical block is stored, another field 112 identifying the flash page within the block and a field 114 identifying the offset within the flash page that identifies where the logical block data begins in the identified flash page. The large size of the map table 104 prevents the table from being held inside the SSD controller. Conventionally, the large map table 104 is held in an external DRAM connected to the SSD controller. As the map table 104 is stored in volatile DRAM, it must be restored when the SSD powers up, which can take a long time, due to the large size of the table.
When a logical block is read, the corresponding entry in the map table 104 is read to determine the location in Flash memory to be read. A read is then performed to the Flash page specified in the corresponding entry in the map table 104. When the read data is available for the Flash page, the data at the offset specified by the map entry is transferred from the SSD to the host. When a logical block is written, the corresponding entry in the map table 104 is updated to reflect the new location of the logical block. It is to be noted that when a logical block is written, the Flash memory will initially contain at least two versions of the logical block; namely, the valid, most recently written version (pointed to by the map table 104) and at least one other, older version thereof that is stale and is no longer pointed to by any entry in the map table 104. These “stale” data are referred to as garbage, which occupies space that must be accounted for, collected, erased and made available for future use.
The TRIM Command
The SATA protocol defines a “TRIM” command specifically for use with Flash-based SSDs. The TRIM command may reduce Write Amplification (WA) by reducing the garbage collection overhead. TRIM is a command that is issued by a host Operating System (OS) to indicate that one or more logical blocks are no longer used and may be deleted. Conventionally, to implement the TRIM command, the following sequence may be followed:
a. The current free space for the block in which the TRIMed logical block is located may be increased by the size of the TRIMed logical block.
b. The logical-to-physical map maintained in volatile memory is then updated to indicate that the logical block in question has been TRIMed.
c. When garbage collecting a block having TRIMed logical blocks, the logical blocks that have been TRIMed are not relocated.
d. When a TRIMed logical block is read, data is not read from Flash memory, but a predetermined string or code is returned (such as all 0's, for example).
e. If the host writes to a TRIMed block, data may be written as normal except that the amount of space freed will be 0.
In conventional SSDs implementing the conventional logical-to-physical addressing scheme, the entry to be TRIMed in the map table 104 must be obsoleted, the map table 104 updated and the updated map table 104 saved in whole or in part, which is inefficient.